#include <iostream>
#include <stdio.h>

#include <iostream>
#include <memory>


template <class T, int size = 100>
class ArrayQueue{
public:
    ArrayQueue();

    ~ArrayQueue();

    bool enqueue(const T&);
    T dequeue();
    bool isFull();
    bool isEmpty();
    void traverse()const;

private:
    int first, last;
    T * storage;
    // int size;
};


template<typename T, int size>
ArrayQueue<T,size>::ArrayQueue()
{
    storage = new T[size];
    first = last = -1;
}

template<typename T, int size>
ArrayQueue<T, size>::~ArrayQueue()
{
    if(storage){
        delete [] storage;
    }
}

template<typename T, int size>
bool ArrayQueue<T,size>::isEmpty()
{
    return first==-1;
}

template<typename T, int size>
bool ArrayQueue<T, size>::isFull()
{
    return first == 0 && last == size-1 || last == first-1;
}

template<typename T, int size>
bool ArrayQueue<T, size>::enqueue(const T& el)
{
    if(!isFull()){
        if(last == -1 || last == size -1){
            storage[0] = el;
            last = 0;
            if(first == -1){
                first = 0;
            }
        }else{
            storage[++last] = el;
        }
        return true;
    }else{
        std::cout<<"Queue full."<<std::endl;
        return false;
    }
}

template<typename T, int size>
T ArrayQueue<T, size>::dequeue()
{
    if(isEmpty()){
        std::cerr<<"Queue empty."<<std::endl;
        exit(1);
    }
    T temp = storage[first];
    if(first == last){
        first = last = -1;
    }else if( first == size -1){
        first = 0;
    }else{
        ++first;
    }
    return temp;
}


template<typename T, int size>
void ArrayQueue<T, size>::traverse()const
{
	for (auto i = first; i <= last; ++i)
	{
		std::cout << storage[i] << " ";
	}
	std::cout << std::endl;
}

int main(int argv, char**argc)
{
    printf("************  test hello zc!!!   **************\n");
    /* add test code! */

    ArrayQueue<int, 3> queue;

	queue.enqueue(10);
	queue.enqueue(10);
	queue.enqueue(10);

	std::cout << queue.isFull() << std::endl;

	queue.traverse();
	queue.dequeue();
	queue.traverse();
	queue.dequeue();
	std::cout << queue.isEmpty() << std::endl;
	queue.dequeue();
	std::cout << queue.isEmpty() << std::endl;
    
    return 0;
}
